package com.xiaoyu.binaryTree;

/**
 * @program: DS_and_A
 * @description:
 *
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 *
 * 本题中，一棵高度平衡二叉树定义为：
 *
 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
 *
 *
 * @author: YuWenYi
 * @create: 2021-05-20 09:10
 **/
public class IsBalanced_110 {

    //自顶向下的方法,其时间复杂度最高为O(n^2).因为会重复的调用height函数
    public boolean isBalanced1(TreeNode root) {
        if (root == null){
            return true;
        }
        if (Math.abs(height1(root.left) - height1(root.right)) > 1){
            return false;
        }
        return isBalanced1(root.left) && isBalanced1(root.right);
    }
    public int height1(TreeNode node){
        if (node == null) return 0;
        return Math.max(height1(node.left), height1(node.right)) + 1;  //不需要判断node.left和right是否为空,因为上面的if会判断
    }

    //由于第一种方法的缺陷,因此我们需要及时止损,从自底向上的方法,去遍历二叉树
    //这样的时间复杂度稳定在O(n),更加快捷(类似后序遍历)
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }
    public int height(TreeNode node){
        if (node == null) return 0;
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }
        return Math.max(height(node.left), height(node.right)) + 1;
    }


    public static void main(String[] args) {
        IsBalanced_110 balanced110 = new IsBalanced_110();
        TreeNode right = new TreeNode(3,new TreeNode(6),new TreeNode(7));
        TreeNode left = new TreeNode(2,new TreeNode(4),new TreeNode(5));
        TreeNode root = new TreeNode(1,left,right);

        System.out.println(balanced110.isBalanced(root));
    }
}
